package com.wenlin.myproduction.util;

import java.util.ArrayList;
import java.util.List;

/**
 * @author 文琳
 * @Email 377979485@qq.com
 * @desc 有一只跳蚤的家在数轴上的位置 x 处。请你帮助它从位置 0 出发，到达它的家。
 * <p>
 * 跳蚤跳跃的规则如下：
 * <p>
 * 它可以 往前 跳恰好 a 个位置（即往右跳）。
 * 它可以 往后 跳恰好 b 个位置（即往左跳）。
 * 它不能 连续 往后跳 2 次。
 * 它不能跳到任何 forbidden 数组中的位置。
 * 跳蚤可以往前跳 超过 它的家的位置，但是它 不能跳到负整数 的位置。
 * <p>
 * 给你一个整数数组 forbidden ，其中 forbidden[i] 是跳蚤不能跳到的位置，同时给你整数 a， b 和 x ，请你返回跳蚤到家的最少跳跃次数。如果没有恰好到达 x 的可行方案，请你返回 -1 。
 * <p>
 *  
 * <p>
 * 示例 1：
 * <p>
 * 输入：forbidden = [14,4,18,1,15], a = 3, b = 15, x = 9
 * 输出：3
 * 解释：往前跳 3 次（0 -> 3 -> 6 -> 9），跳蚤就到家了。
 * 示例 2：
 * <p>
 * 输入：forbidden = [8,3,16,6,12,20], a = 15, b = 13, x = 11
 * 输出：-1
 * 示例 3：
 * <p>
 * 输入：forbidden = [1,6,2,14,5,17,4], a = 16, b = 9, x = 7
 * 输出：2
 * 解释：往前跳一次（0 -> 16），然后往回跳一次（16 -> 7），跳蚤就到家了。
 *  
 * <p>
 * 提示：
 * <p>
 * 1 <= forbidden.length <= 1000
 * 1 <= a, b, forbidden[i] <= 2000
 * 0 <= x <= 2000
 * forbidden 中所有位置互不相同。
 * 位置 x 不在 forbidden 中。
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode.cn/problems/minimum-jumps-to-reach-home
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 * @time 2022-08-24 星期三 15:49
 */
public class MinimumJumpsUtils {
    public int minimumJumps(int[] forbidden, int a, int b, int x) {
        //回溯法 +a+a-b +a-b+a -b+a+a
        //原题可以变换理解为前进a或者a-b。
        //先找出是否找到组合满足正好能到x位置
        List<Integer> listForbidden = new ArrayList<>();
        for (int f :
                forbidden) {
            listForbidden.add(f);
        }
        int sum = 0;
        int minNumPlusA = Integer.MAX_VALUE;
        int minNumPlusAMinusB = Integer.MAX_VALUE;
        int minStep = Integer.MAX_VALUE;
        for (int i = 0; i < x; i++) {
            for (int j = 0; j < x; j++) {
                sum = i * a + j * (a - b);
                System.out.println("sum=" + sum + ":" + (i + j) + "个a和" + j + "个b");
                if (sum > x + a) {
                    System.out.println("超限");
                    break;
                }
                if (sum == x) {
                    System.out.println("方案：需要" + (i + j) + "个a和" + j + "个b");
                    int step = i + j * 2;
                    if (step < minStep) {
                        minStep = step;
                        minNumPlusA = i;
                        minNumPlusAMinusB = j;
                    }
                }
            }
        }
        //再判断i个a和j个(a-b)任意组合的步数能否全部都不在forbidden数组中。
        int numSingleAAndAMinusB = minNumPlusA + minNumPlusAMinusB;
        //理解成minNumPlusA个a中插入minNumPlusAMinusB个a-b。排列组合问题，等于C_下标minNumPlusA_上标minNumPlusAMinusB
        int cur = 0;
        int [] step = new int [numSingleAAndAMinusB];
        for (int i = 0; i < numSingleAAndAMinusB; i++) {
            step[i] = a;
        }
        //得到一个全是a的数组，将某一个a改成a-b，如果出现forbidden的数则舍弃
        


        return minStep == Integer.MAX_VALUE ? -1 : minStep;
    }
}
